Iosif Stalin sinh ngày 21 tháng 12 năm 1879 theo lịch Gregorius (tức ngày 6 tháng 12 năm 1878 theo lịch Julius) trong một gia đình công nhân đóng giày ở thị trấn Gori của tỉnh Tiflis, Đế quốc Nga, nay thuộc Gruzia. Tên khai sinh của ông trong tiếng Gruzia là Ioseb Besarionis dze Dzhugashvili (იოსებ ბესარიონის ძე ჯუღაშვილი, Ио́сиф Джугашви́ли). Mẹ ông tên là Ketevan Geladze còn cha ông là Besarion Jughashvili, một người thợ sửa giày. Trước Ioseb họ có hai đứa con khác nhưng đều chết yểu.[8]

Khi còn nhỏ Ioseb có nhiều vấn đề về sức khỏe. Ông sinh ra với hai ngón chân trái dính vào nhau.[9] Lên 7 tuổi ông bị đậu mùa và để lại những vết sẹo rỗ cho đến cuối đời. Năm 12 ông bị một tai nạn và tay trái từ đó bị cứng khớp và ngắn hơn tay phải.

Gia đình từng có thời yên ấm cho đến khi Besarion bị nghiện rượu nặng và thường xuyên lạm dụng, đánh đập vợ con.[10] Lên 10 tuổi Ioseb mới bắt đầu học trường dòng nơi học sinh người Gruzia được dạy tiếng Nga, tuy nhiên đến khi trưởng thành giọng Stalin vẫn mang nặng ngữ điệu Gruzia. Cũng khoảng thời gian này cha Ioseb bị trục xuất khỏi Gori do tấn công cảnh sát trưởng địa phương.

Năm 16 tuổi, Ioseb được nhận học bổng vào một Chủng viện Chính thống giáo Gruzia của Tiflis ở Tbilisi. Mặc dù kết quả học tập tốt, Ioseb bị đuổi học năm 1899 sau khi bỏ lỡ kì thi cuối năm. Hồ sơ của chủng viện cũng cho thấy ông đã không thể đóng tiền học.[11]

Khoảng thời gian này, Ioseb đọc được những tác phẩm của Lenin, và gia nhập Đảng Công nhân Xã hội-Dân chủ Nga, một tổ chức Marxist, tới năm 1901 trở thành ủy viên thành ủy Tiflis. Sau khi rời chủng viện, Stalin từng làm công việc thư lại bán thời gian ở một văn phòng khí tượng, nhưng sau một đợt đàn áp của chính quyền, ông rút vào hoạt động ngầm. Ông gia nhập đảng Bolshevik năm 1903 và lấy tên là "Stalin" (Ста́лин), có nghĩa "Mạnh như thép". Trong tiếng Nga, tên đầy đủ của ông là Ио́сиф Виссарио́нович Ста́лин, được chuyển tự là Iosif Vissarionovich Stalin. [12]

Năm 1903, khi Lenin lập ra nhóm Bolshevik bên trong Đảng Công nhân Xã hội Dân chủ, Stalin tích cực tham gia và chứng tỏ mình là một nhà tổ chức hiệu quả cũng như một nhà vận động có tài, vận dụng học vấn và tài làm thơ của mình. Trong thời gian này, Stalin tổ chức rải truyền đơn, kích động bãi công, tiến hành cướp nhà băng cũng như các vụ ám sát chống chế độ Sa hoàng. Vụ cướp nổi tiếng nhất là vào ngày 26 tháng 6 năm 1907 tại Tiflis, với sự giúp đỡ của một tay trong là bạn học cũ của Stalin, cướp đi số tiền lên đến 341 ngàn rúp (trị giá hơn 3 triệu đôla Mỹ theo tỷ giá hiện nay), có vai trò quan trọng của Stalin trong việc lập kế hoạch dù ông không tham gia vào[13].

Từ năm 1902 cho đến năm 1913 Stalin bị bắt tất cả bảy lần, nhiều lần bị đày sang Siberia, trong đó 5 lần vượt ngục. Trong Cách mạng Nga (1905), ông chiến đấu cho đảng Bolshevik. Tháng 1-1912, trong Hội nghị toàn Nga lần VI của Đảng Công nhân xã hội dân chủ, Stalin đã được bầu vắng mặt vào Ban Chấp hành Trung ương Đảng.[14]

Stalin kết hôn lần đầu với Ekaterina Svanidze năm 1906 và có một người con. Bà chết ngay năm sau đó do bệnh sốt phát ban. Năm 1911, ông gặp vợ tương lai thứ hai, Nadezhda Alliluyeva, trong một lần bị đi đày ở Siberia.